package com.ljx.offer;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * 最高的字符长度是
 * @author 李捷禧
 * Date: 2023/3/17
 * ClassName: C_50
 */

public class C_50 {


    /**
     * 这个3ms
     * hashMap 29ms
     * @param s
     * @return
     */
    public char firstUniqChar2(String s) {
        char[] arr = s.toCharArray();
        // 只会出现小写, 不需要用到map，只需要一个数据表示是否出现几次就可以了
        int[] flag = new int[26];
        for (char a : arr) {
            flag[a - 'a']++;
        }
        for (char a : arr) {
            if (flag[a - 'a'] == 1) {
                return a;
            }
        }
        return ' ';
    }

    /**
     * 使用哈希表来存储，如果hashmap中key没有重复的就返回true
     * @param s
     * @return
     */
    public char firstUniqChar(String s) {
        HashMap<Character, Boolean> hashMap = new HashMap<>();
        char[] arr = s.toCharArray();
        for (char c : arr)
            hashMap.put(c,!hashMap.containsKey(c));
        for (char c : arr) {
            if(hashMap.get(c)) return c;
        }
        return ' ';
    }

    /**
     * 运行超时？
     * 解决
     * @param s
     * @return
     */
    public char firstUniqChar1(String s) {
        char[] arr = s.toCharArray();
        for (char a : arr) {
            // 你这个里面调用的是String的方法，本质还是搜索了一遍，所以时间复杂度是n^2
            if(isContains(s,a,s.length())){
                return a;
            }
        }
        return ' ';
    }
    boolean isContains(String s,char a,int len){
        String s1 = s.replace(Character.toString(a), "aa");
        if(s1.length() > (len + 1)) return false;
        else return true;
    }

    @Test
    public void test(){
        String str = "ausbasc";
        System.out.println(firstUniqChar1(str));
//        String replace = str.replace("a", "aaaa");
//        System.out.println(replace);
    }

}
